import random
import time

def sort(l:list):
    length = len(l)
    h = 1
    while h < length // 3:
        h = h * 3 + 1
    while h >= 1:
        for i in range(h, length):        
            for j in range(i, 0, -h):
                if l[j] >= l[j - h]:
                    break              
                else:
                    l[j], l[j - h] = l[j - h], l[j]
        h = h // 3

if __name__ == "__main__":

    l = [random.randint(0,50000) for _ in range(50000)]
    before = time.time()
    sort(l)
    after = time.time()
    print(after - before)   